HW#2 --- last modified February 28 2019 22:31:40..

Solution set.

Due date: Oct 7

Files to be submitted:
  Hw2.zip

Purpose: To learn more about the syntax of programming languages by writing an interpreter for a simple functional language based on expression evaluation.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

(5) [Read and produce context-free grammars.]

(6) [Write recursive-descent parsers for simple languages, by hand or with a parser generator.]

(8) Write interpreters for simple languages that involve arithmetic expressions, bindings of values to names, and function calls.

Specification:

For this homework you will write an interpreter for the programming language Stringline. To grade your homework, the grader will unzip your Hw2.zip file and briefly look through your source code. Then the grader will type within the Hw2 folder the command "make clean; make all" to compile your project. Test Stringline programs will be copied into your Hw2 folder and run with commands like:

./Stringline filename_1

./Stringline filename_2

...

Stringline is a made up programming language for the purpose of this assignment. The name comes from straight-line programs which are considered in circuit complexity and word problems for groups. I wanted to create a language which to interpret was only slightly different than the expression evaluation -- we'll go over expression evaluation in class and it is in the book. On the other hand, I thought it would be cool if we could write an interpreter for a language which is likely to be Turing complete. As we'll have just talked about Flex and Bison by the time this homework is due, you can either do brute-force parsing or use Flex and Bison for this assignment. For Hw3 I will make you use these tools.

A program in Stringline consists of a sequence of labeled statements or comments. Programs without labeled statement are viewed as trivial and do nothing. A comment consists of a single line beginning with a ';'. A labeled statement has the form :

label : anonymous-statement

where an anonymous-statement has the form:

(operation arg_1 arg_2 ... arg_n)

In the above I have used a single-space to denote white-space (such as spaces, tabs, linefeeds, formfeeds, carriage-returns) of one or more characters. Whitespace is ignored in Stringline except where we use it to delimit labels and other tokens. So a labeled statement which looks like:

label : 
   (operation 
       arg_1 
       arg_2
       ... 
       arg_n
   )

is completely legal. Notice given the way we have defined things above you cannot embed a comment in a labelled statement. So:

; a comment saying what 
; label does
label : 
   (operation 
       arg_1 
       arg_2
       ... 
       arg_n
   )

is legal. But,

label : 
   (operation ; a comment within a labeled statement is not.
       arg_1 
       arg_2
       ... 
       arg_n
   )

is not.

A label is any string made up of the letters a-z, A-Z, 0-9, '_', or '-'.

An operation is either a label or one of the following reserved words: #first, #rest, #append, #isequal, #echo, #input, or #exit. So "echo" is a label, but "#echo" is a reserved word.

An argument is either an anonymous statement, a parameter variable, or a string literal.

A parameter variable consists of a dollar sign followed by a nonzero integer. For example, $0, $1, $2, ...

A string literal is any sequence of characters beginning with a double-quote and terminated by the first double-quote not immediately preceded by a backslash. So string literals may be written over several lines:

" fgdfgn
fgdjg \" sfdgj
fdsgkl
"

is a legal string literal. Notice also the string \\" is still an escaped double-quote so would not terminate a string. i.e., the only character where escaping has an effect is double-quote.

Evaluation of a Stringline program is as follows: The interpreter scans from the start of the file to the first labeled statement and tries to evaluate it. When evaluation of this labeled statement is done the program terminates. To evaluate a labeled statement one first evaluates each argument as it is needed. Then one applies the operation to the result. For each of the reserved words, here is what it means to apply the operation to the arguments and which arguments will need to be evaluated:

#first - If no arguments are supplied it returns the empty string. Otherwise, it looks at the left-most argument in its argument list, evaluates that, and ignores the rest. It then returns only the first character, of what this leftmost argument evaluates to.

#rest - If no arguments are supplied it returns the empty string. Otherwise, it looks at the left-most argument in its argument list, evaluates that, and ignores the rest. It then returns the substring of that string consisting of all but the first character.

#append - If no arguments are supplied it returns the empty string. Otherwise, it returns the string that results from appending each of the evaluated arguments of its argument list from left to right.

#isequal - If fewer than four arguments are supplied it returns the empty string. Otherwise, it checks if the left-most and next to left-most arguments evaluate to the same string. If they do it evaluates the third left-most argument, and returns that. If they don't then it evaluates and returns the fourth argument from the left.

#echo - This evaluates each of its arguments in turn. When it gets the value of an argument, it echoes it immediately to the terminal and then evaluates the next argument. This operation returns as its value the same result append would if applied to the same list.

#input - ignores and does not evaluate its arguments, gets one line of input from the terminal, and returns that as a string less the end of line character.

#exit - ignores and does not evaluate its arguments, terminates the program.

If the operation is a label rather than a reserved word, then one evaluates each of the arguments in its argument list first. Call the result of this the calling list. Then one scans from the start of the program to the first labeled statement that uses that label. Call this statement the receiving statement. One binds any parameter variables in the receiving statement with the corresponding argument from the calling list, even if the parameter variable is nested in some anonymous statement. So the variable $0 would get the value of the leftmost argument in the calling list. If there isn't a corresponding value in the calling list, then one binds the parameter variable to the empty string "". One can imagine this binding is done recursively, for each argument in the receiving statements argument list, if the argument is a parameter variable bind(calling variable, parameter variable) replaces parameter variable with the calling variable if the argument is an anonymous statement then we apply the bind function to each of its arguments. Finally, after binding occurs one evaluates the resulting statement and returns the result. Note this should support recursive calls.

It could be the case that the first labeled statement in the program has parameter variables. If this is the case when Stringline runs and tries to initially evaluate this labeled statement pretend the calling list is empty, so each of these parameter variables will get the value of the empty string on this first call.

Here are some example Stringline programs:

; Program 1
; cycles around in a loop till something other than y typed
main : 
(#echo
  "Welcome to Stringline.

"

  "Hit y to see the introductory message again.
"

  (#isequal (#input) "y" (main) (#exit))

)

;end Program 1

; Program 2
; this example takes a string and writes it backwards
main :
(#echo

   "Please enter a string to reverse:
"

   (reverse (#input))
)

; this is where we do the actual reversing
reverse :
(#isequal $0 "" 
   ""
   (#append (reverse (#rest $0)) (#first $0)) 
)
;end Program 2

This completes the description and examples of Stringline, as a place to get started, before you code, you should write a context-free grammar in BNF for Stringline, and put this in your Hw2.zip in a file named grammar.txt.

Point Breakdown